package org.example.myleet.p851;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * 思路：DFS+记忆化搜索
     * 将题目给的有钱关系重构成一个多叉树的树状结构
     * 每个节点里面包含比自己富有的节点，节点中记录当前节点id（person）
     * 另外记录一个记忆，就是当前节点中不比自己穷的最安静节点的id（quietestRicher）
     * 查询某个节点的记忆时，如果还没有记忆，则进行一次DFS，以构建记忆，总的访问节点次数=节点数n
     */
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        //每个几点有一个对应自己的模型
        RichRelation[] persons = new RichRelation[n];
        for (int i = 0; i < n; ++i) {
            //初始化
            persons[i] = new RichRelation(i);
        }
        for (int[] relation : richer) {
            //构建多叉树
            persons[relation[1]].richerList.add(persons[relation[0]]);
        }
        int[] result = new int[n];
        for (int i = 0; i < n; ++i) {
            //DFS+记忆化搜索
            result[i] = persons[i].getQuietestRicher(quiet);
        }
        return result;
    }

    private static class RichRelation {
        //当前节点id
        int person;
        //比自己富有的节点
        List<RichRelation> richerList;
        //当前节点中不比自己穷的最安静节点的id
        Integer quietestRicher;

        public RichRelation(int person) {
            this.person = person;
            richerList = new ArrayList<>();
        }

        //DFS+记忆化搜索
        public int getQuietestRicher(int[] quiet) {
            if (null == quietestRicher) {
                //还没有记忆，DFS构建记忆
                if (richerList.size() != 0) {
                    //当前节点存在比自己富有的节点，则从这些节点中查询其最安静的富有节点的安静值并比较
                    int quietest = quiet[person];
                    int quietestPerson = person;
                    for (RichRelation relation : richerList) {
                        int relationQuietestPerson = relation.getQuietestRicher(quiet);
                        int relationQuietest = quiet[relationQuietestPerson];
                        if (quietest > relationQuietest) {
                            //找到更安静的富有节点，更新候选节点
                            quietest = relationQuietest;
                            quietestPerson = relationQuietestPerson;
                        }
                    }
                    //候选节点成为记忆
                    quietestRicher = quietestPerson;
                } else {
                    //当前节点没有更富有的节点，最安静的人就是自己
                    quietestRicher = person;
                }
            }
            //有记忆，直接返回
            return quietestRicher;
        }
    }
}
